package leetcode.editor.cn;
 
/**
 * 打家劫舍
 * @author qulq
 * @date 2024-07-14 22:26:56
 */
public class T198_HouseRobber{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T198_HouseRobber().new Solution();
	 }

	/**
	 * 最后一步：最后一个房屋偷或者不偷
	 * f[i]：前i个房屋，能偷到的最大价值
	 * f[i] = max(f[i], f[i-2] + Ai)
	 * f[0] = 0，没有房屋、能偷的金额为0
	 * f[1] = A1,偷
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
		int[] dp = new int[nums.length + 1];
		dp[0] = 0;
		dp[1] = nums[0];
		for (int i = 2; i <= nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		return dp[nums.length];
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}